/*
    XTU OJ: 1355
    by: fifth_light
*/

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

#define N 3000050
#define sqrtN 1733

char B[N + 20] = {0};
int C[N + 20];
int64_t D[N + 20];

void prepare() {
    B[0] = 1;
    B[1] = 1;
    for (int i = 2; i < sqrtN; i == 2 ? (i = 3) : (i += 2)) {
        for (int n = i; n < N; n += i) {
            if (i != n) B[n] = 1;
        }
    }
    for(int i = 2; i <= N; i++) {
        if (!B[i]) {
            C[i] = i-1;
        }
    }
    for(int i = 2; i <= sqrtN; i++) {
        if (!B[i]) {
            for(int j = i * i; j <= N; j += i) {
                int p = j / i;
                if (p % i == 0) {
                    C[j] = C[p] * i;
                } else {
                    C[j] = C[p] * (i - 1);
                }
            }
        }
    }
    int64_t sum = 0;
    for (int i = 0; i < N; i++) {
        D[i] = (sum += C[i]);
    }
}

int main(void) {
    prepare();
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%" PRId64 "\n", D[b] - D[a - 1] + (a == 1 ? 1 : 0));
    }
    return 0;
}
